package 中等.滑动窗口;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 */
public class 无重复字符的最长子串_3 {

    public static void main(String[] args) {

        System.out.println(lengthOfLongestSubstring2("cdd"));

    }

    /**
     * 队列+哈希表
     * 如果当前字符存在于队列中，那么将队首字符，出队列，直到将当前字符，不存在队列中为止
     * 将当前字符加入到队尾，哈希表用于快速查询，当前字符是否存在于队列中
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        Deque<Character> queue = new ArrayDeque<>();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                while (!queue.isEmpty() && queue.peek() != c) {
                    set.remove(queue.pollFirst());
                }
                queue.pollFirst();
            }
            queue.addLast(c);
            set.add(c);
            maxLen = Math.max(maxLen, queue.size());
        }
        return maxLen;
    }

    /**
     * 滑动窗口
     * 队列可以使用 两个指针 代替
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        int maxLen = 0;
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0;
        while (right < s.length()) {
            while (right < s.length() && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                // 能进循环，说明 [left,right] 是不存在重复元素的
                maxLen = Math.max(maxLen, right - left + 1);
                right++;
            }

            // 特判，说明到末尾，[left,right-1]区间没有产生重复元素
            if (right == s.length()) {
                maxLen = Math.max(maxLen, right - left);
                return maxLen;
            }

            char repeatC = s.charAt(right);
            while (left < right && s.charAt(left) != repeatC) {
                set.remove(s.charAt(left));
                left++;
            }

            // s.charAt(left) 为多余的重复元素
            left++;
            maxLen = Math.max(maxLen, right - left + 1);
            // 右边界向右
            right++;
        }
        return maxLen;
    }

}
